import java.util.Arrays;

/*
*  快速排序
* */
public class quickSort {

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int midThree(int[] arr, int start, int end) {
        int mid = (start + end) / 2;
        if (arr[start] > arr[end]) {
            if (arr[mid] > arr[start]) {
                return start;
            } else if (arr[mid] < arr[end]) {
                return end;
            } else {
                return mid;
            }
        } else {
            if (arr[mid] > arr[end]) {
                return end;
            } else if (arr[mid] < start) {
                return start;
            }else {
                return mid;
            }
        }
    }

    // 插入排序
    private static void insertSort(int[] arr, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int temp = arr[i];
            int j;
            for ( j = i - 1; j >= start  ; j--) {
                if (arr[j] > temp) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = temp;
        }
    }


    private static void sort(int[] arr) {
        quick2(arr, 0, arr.length-1);
    }

    private static void quick(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int partition = partition3(arr, start, end);
        // 左边
        quick(arr, start, partition-1);
        // 右边
        quick(arr, partition+1, end);
    }


    // 快速排序优化， 三数取中法
    private static void quick2(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        // 使用这个优化， 主要解决 数据量太大，递归多的情况， 这个就可以减少递归的次数
        if (end - start + 1 <= 14) { // end - start + 1 是算出总共有多少数据，数据越少越趋于有序
            // 插入排序
            insertSort(arr, start, end);
            return;
        }

        int index = midThree(arr, start, end);
        swap(arr, index, start);

        int partition = partition3(arr, start, end);
        // 左边
        quick2(arr, start, partition-1);
        // 右边
        quick2(arr, partition+1, end);
    }




    // 挖坑法
    private static int  partition(int[] arr, int left, int right) {
        int temp = arr[left];
        while (left < right) {
            while ((left < right) && (arr[right] >= temp)) { // 为什么要取 >= 不取 >, 因为如果遇到了和基准值一样的值，arr[right] > temp 容易变成死循环
                right--; // 先从 end 开始走 是为了在最后交换的时候 一定是左边找到比基准值小的数值 在循环停下来 最后再交换基准值
            }
            arr[left] = arr[right];
            while ((left < right) && (arr[left] <= temp)) {
                left++; // 如果是 先从 start 开始走，在循环结束后，是 start 停止的位置和基准值交换， start 是找比基准值大的数值，容易造成 比基准值大的数值 放在了右边的区域
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }


    // Hoare
    private static int  partition2(int[] arr, int left, int right) {
        int i = left;
        int temp = arr[left];
        while (left < right) {
            while ((left < right) && (arr[right] >= temp)) { // 为什么要取 >= 不取 >, 因为如果遇到了和基准值一样的值，arr[right] > temp 容易变成死循环
                right--;
            }
            while ((left < right) && (arr[left] <= temp)) {
                left++;
            }
            int temp2 = arr[left];
            arr[left] = arr[right];
            arr[right] = temp2;
        }
        arr[i] = arr[left];
        arr[left] = temp;

        return left;
    }

    // 前后指针法
    private static int  partition3(int[] arr, int left, int right) {
       int prev = left;
       int cur = left + 1;
       while (cur <= right) {
           if ((arr[cur] < arr[left]) && arr[++prev] != arr[cur]) {
               int temp = arr[cur];
               arr[cur] = arr[prev];
               arr[prev] = temp;
           }
           cur++;
       }
       int temp = arr[prev];
       arr[prev] = arr[left];
       arr[left] = temp;
       return prev;
    }



    public static void main(String[] args) {
        int[] arr = {5, 7, 6, 4, 3, 1, 2, 9, 2, 22, 33, 44, 66, 77, 33, 45};
        int[] arr2 = {1, 2, 3, 4, 5, 6 ,7};
        int[] arr3 = {7, 6, 5, 4, 3, 2, 1};
        sort(arr);
        System.out.println("乱序: " + Arrays.toString(arr));
        sort(arr2);
        System.out.println("顺序: " + Arrays.toString(arr2));
        sort(arr3);
        System.out.println("逆序: " + Arrays.toString(arr3));
    }
}
